package com.adee.zingfront;

/**
 * 算法题：力扣有一道机器人走方格（二维）的题目（可自行百度搜索学习），假如在三维空间中，给定长宽高为 l、m、
 * n（单位长度仍为 1），机器人只能向右，向上，向前走，如图所示，从 start 到 finish 有多少种走法？
 *
 * 思路：动态规划
 * 定义int[][][] dp;  dp[i][j][k]表示从坐标(0,0,0)到达坐标为(i,j,k)共有多少种走法。
 * 递推公式：dp[i][j][k] = dp[i][j][k-1] + dp[i][j-1][k] + dp[i-1][j][k];
 * 首先将i=0、j=0、k=0三个面初始化，然后在递推计算其余坐标。
 */
public class Test4 {
    public static void main(String[] args) {
        int l = 10, m = 10, n = 10;
        int[][][] dp = new int[l][m][n];
        // 初始化
        // 三条线
        for (int i = 0; i < l; i++) {
            dp[i][0][0] = 1;
        }
        for (int j = 0; j < m; j++) {
            dp[0][j][0] = 1;
        }
        for (int k = 0; k < l; k++) {
            dp[0][0][k] = 1;
        }
        // 三个面
        for (int i = 1; i < l; i++) {
            for (int j = 1; j < m; j++) {
                dp[i][j][0] = dp[i-1][j][0] + dp[i][j-1][0];
            }
        }
        for (int i = 1; i < l; i++) {
            for (int k = 1; k < n; k++) {
                dp[i][0][k] = dp[i-1][0][k] + dp[i][0][k-1];
            }
        }
        for (int j = 1; j < m; j++) {
            for (int k = 1; k < n; k++) {
                dp[0][j][k] = dp[0][j-1][k] + dp[0][j][k-1];
            }
        }
        // 递推
        for (int i = 1; i < l; i++) {
            for (int j = 1; j < m; j++) {
                for (int k = 1; k < n; k++) {
                    dp[i][j][k] = dp[i][j][k-1] + dp[i][j-1][k] + dp[i-1][j][k];
                }
            }
        }

        int[] start = new int[]{3,3,3};
        int[] finish = new int[]{6,7,8};
        // 打印结果
        System.out.println(dp[finish[0]-start[0]][finish[1]-start[1]][finish[2]-start[2]]);
    }
}
